//二叉搜索树中的中序后继  

//非递归
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) 
    {
        stack<TreeNode*> st;
        TreeNode* cur=root,*pre=nullptr;
        //如果pre==p 则返回 cur
        while(!st.empty() || cur)
        {
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            TreeNode* top=st.top();
            st.pop();
            if(pre==p)
            {
                return top;
            }
            pre=top;
            cur=top->right;
        }
        return nullptr;
    }
};

//递归
class Solution {
public:
    TreeNode* res;
    TreeNode* prefix=nullptr;
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) 
    {
        //思路 中序遍历 使用一个变量记录当前节点的前一个节点
        //当 当前的节点的前一个节点==p时 记录当前节点
        fun(root, p);
        return res;
    }
    void fun(TreeNode* root, TreeNode* p) 
    {
        if(!root) return;
        fun(root->left, p);
        if (prefix == p) res = root;
        prefix = root;
        fun(root->right, p);    
    }
};


//图像渲染
class Solution 
{
public:
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

    void dfs(vector<vector<int>>&image,vector<vector<int>>&already ,int row,int col,int curx,int cury,int oldcolor,int newcolor)
    {
        //修改当前位置的颜色
        image[curx][cury]=newcolor;
        already[curx][cury]=1;//表示已经修改过了
        //修改上下左右
        for(int i=0;i<4;i++)
        {
            int newx=curx+arr[i][0];
            int newy=cury+arr[i][1];
            if(newx>=row || newx<0 ||newy>=col ||newy<0)
            {
                //已经出去了
                continue;
            }
            //判断新的位置需不需要渲染
            if(image[newx][newy]==oldcolor && already[newx][newy]==0)
            {
                dfs(image,already,row,col,newx,newy,oldcolor,newcolor);
            }
        }


    }
    vector<vector<int>> floodFill(vector<vector<int>>& image,int sr, int sc, int color) 
        {
            if(image.empty())
            {
                return vector<vector<int>>();
            }
            int row=image.size();
            int col=image[0].size();
            vector<vector<int>>already(row,vector<int>(col,0));//判断位置是否被修改过
            int oldcolor=image[sr][sc];
            dfs(image,already,row,col,sr,sc,oldcolor,color);
            return image;
        }
};
